package algorithm.shipinke;

/**
 * algorithm.leetcode 300
 */

public class LISRecursion {
    static int max;

    public int f(int[] nums, int n) {
        /**
         * 在数组nums中的前n个数字子串中的最长上升子序列
         */
        if (n <= 1) {
            return n;
        }

        int result = 0, maxEndingHere = 1;

        for (int i = 1; i < n; i++) {
            result = f(nums, i);

            if (nums[i-1] < nums[n-1] && result + 1 > maxEndingHere) {
                maxEndingHere = result + 1;
            }
        }

        if (max < maxEndingHere) {
            max = maxEndingHere;
        }
        return maxEndingHere;
    }

    public int LIS(int[] nums) {
        max = 1;
        f(nums, nums.length);
        return max;
    }

    public static void main(String[] args) {
        LISRecursion lis = new LISRecursion();
        int[] nnn = {10, 9, 2, 5, 3, 7, 101, 4};
        System.out.println(lis.LIS(nnn));
    }
}
